package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-10-04
 * 子数组最大平均数 I
 */
public class FindMaxAverage {
    /**
     * 主
     * 输入：nums = [1,12,-5,-6,50,3], k = 4
     * 输出：12.75
     * 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
     * \
     * 输入：nums = [5], k = 1
     * 输出：5.00000
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindMaxAverage findMaxAverage = new FindMaxAverage();
        int[] nums = new int[]{1, 12, -5, -6, 50, 3};
        int k = 4;
        System.out.println(findMaxAverage.findMaxAverage(nums, k));
    }

    /**
     * 查找最大平均值:滑动窗口
     * 测试用例通过，但是超时
     *
     * @param nums nums
     * @param k    k
     * @return double
     */
    public double findMaxAverage(int[] nums, int k) {
        int left = 0, right = k - 1;
        int len = nums.length - 1;
        //指定负无穷大
        double avg = Double.NEGATIVE_INFINITY;
        while (right <= len) {
            avg = Math.max(avg, this.helper(nums, left, right));
            left++;
            right++;
        }
        return avg;
    }

    /**
     * 计算平均值助手类
     *
     * @param nums  nums
     * @param left  左
     * @param right 右侧
     * @return double
     */
    private double helper(int[] nums, int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return (double) sum / (right - left + 1);
    }

    /**
     * 滑动窗口，采取减去划走的 加上进来的计算
     *
     * @param nums nums
     * @param k    k
     * @return double
     */
    public double findMaxAverage2(int[] nums, int k) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i = k; i < n; i++) {
            sum = sum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, sum);
        }
        return 1.0 * maxSum / k;
    }


}
